@LoyFan

mathjax:true
TROPICAL GEOMETRY, NEURAL NETWORKS, AND LOW-COHERENCE FRAMES

摘要

这篇文章的工作分为三个方面

建立起前馈神经网络和Tropical几何的联系

我们发现，激活函数设置为ReLu（修正线性单元）的前馈神经网络实际上是一个Tropical有理函数。
本文展示了ReLu神经网络得到的决策边界是包含在一个和这个网络相关联的Tropical多项式的Tropical超平面内。
我们把由前馈神经网络代表的函数和多面体联系起来。
本文展示了两层网络可以完全以zonotopes为特征，zonotopes也可以作为更深层网络的建造块。
多面体的顶点数量给出了这个网络对应的函数的线性区域的数量的上界。
本文展示了这个上界在网络层数的影响下呈指数增长，但和每一层的隐藏节点数量只是多项式相关。

提出了一种基于内容的神经记忆访问的连续型向量空间中的attention模型。

本模型将知识图谱实体表示为低维向量，而将上下文相关attention表示为向量空间中的高斯评分函数。
我们应用这个模型来完成任务，比如知识图谱补全、复杂问题回答。
这个提出的attention模型能用自然的方法解决“一系列的关系后的不确定性的传播”和“条件的结合”。
使用参加2014FIFA世界杯的足球运动员的数据库，我们证明了我们的模型能够很好地解决路经查询和连接查询。

第三部分研究了非交换群作用下循环向量生成的有限复框架。

我们检查了与群的冯-诺依曼代数有关的算子空间中的群框架。然后将寻找一个适当的循环向量转化为寻找一个凸集的交集，该凸集规定了相干性约束和Hermitian秩1算子的子集。采用交替投影算法搜索其交集，并采用启发式外推法加速计算。
在实验中，我们将模型应用于海森堡群和有限仿射群。在海森堡群的情况下，我们的方法能够找到产生等角度紧帧的循环向量，达到数值精度。

概览

深层神经网络的兴起在理论和应用上激发了很多新的研究方向。本文的第一个工作建立了前馈神经网络和Tropical几何学的联系。Tropical几何学是一个新兴的、快速发展的代数几何学领域，但迄今为止它和AI的关联还不大，通过和神经网络的联系，可以从前者解决后者的问题，为研究提供了机会。

第二章建立了神经网络的Tropical视角，证明了具有ReLu激活函数的前馈神经网络相当于Tropical有理函数的半场（semi-field）。另外发现具有一个隐藏层的神经网络可以用zonotopes来表示，同时zonotopes也是深层神经网络的建造基础块。还有，由神经网络导出的决策边界和Tropical超平面相关联。还发现深度神经网络的线性区域到多面体的顶点和Tropical有理函数相关联。

利用Tropical几何的工具对深层神经网络的指数表示进行了概括，并表明了深层网络能够比浅层网络将域划分为更多的指数线性区域。

第三章提出了一种知识图谱表示的embedding模型。

在第四章中，我们研究了循环向量在非交换群作用下产生的框架。非交换群是许多著名的框架和正交系统构造的基础。

以Tropical几何的角度分析深度神经网络

介绍

深层神经网络最近在人工智能、计算机视觉、语音识别、自然语言处理等不同领域取得了巨大的成功，但在理论和数学理解上还有未完成的工作。早期的研究表明深层架构可以有效地用户表达复杂的函数群，同时仍然保持相对简单的结构。一个深层神经网络更有效地使用它的参数，并且因此需要指数更少的参数去表示确定的函数族。从经验上表明，当网络足够大时，几个成功的神经网络可以粉碎训练集。另外，这些模型虽然具有很高的表示能力，但同时也具有规则化和“简单”的特点，即它们概括为训练阶段看不到的数据。解释神经网络的这些特性，并找到正确的形式化复杂度度量方法来捕获它们的泛化能力，仍然是一个挑战。

在本文中，我们关注点在具有ReLu激活函数的前馈神经网络，它是最基础的神经网络，并且也是深度学习中最广泛使用的（也许和递归或卷积神经网络一起使用）类型的神经网络之一。

我们展示了在Tropical代数或者Tropical代数几何中，这样一个神经网络是一个有理函数的类似物，换言之，是两个多元多项式f,g的比值，$f(x_1,…,x_d) / g(x_1,…,x_d)$。

这是一个代数几何中的新领域，在近十年来爆炸式成长，但是在纯数学之外还是相对模糊。事实上，深度学习和Tropical代数几何是相关的，对我们来说是一个惊喜的发现。

我们讨论的多项式是“tropical多项式”。对于通常的三角多项式来说，我们知道要做有理逼近-用两个多项式的比值而不是一个多项式来近似函数-可以在不增加次数的情况下极大地提高逼近质量。这给了我们思路：一个神经网络是两个Tropical多项式的比值，换言之，一个Tropical有理函数。更严谨地说，如果我们把一个神经网络看做一个函数：

$V:R^d → R^p$ $x = (x_1,...,x_d)→(v_1(x),...,v_p(x))$

其中每一个$v_i$是一个Tropical有理函数。从此以后，“一个神经网络是（某种实值函数）”类型的陈述要用协调的意义来解释——这个神经网络的每一个输出节点都是一个输入节点的一个函数。

事实上，对于神经网络的分类问题中出现的特殊情况$p = 1$，我们表明：

激活函数为ReLu的前馈神经网络代表的函数族和Tropical有理函数族相同。

我们的主要目标是演示新理论如何用于分析神经网络。除此之外，这使我们能够捕获神经网络所表示的函数的复杂性以及在分类问题中从它派生的决策边界的复杂性，或者更重要的是，随着层数的增加，这种复杂性是如何变化的。神经网络所代表的函数的复杂性可以通过神经网络所具有的线性区域的数量来捕获，该区域可以通过计算由与神经网络相关的Tropical多项式构造的多面体上的顶点数量来研究。在分类问题中，由神经网络导出的决策边界将输入空间划分为若干区域，它是Tropical超曲面的一个子集——一个分段线性多面体曲面。

Tropical几何学允许我们在这些数字上得出一个上限，从而测量其几何学的复杂性。当神经网络的深度和输入维数固定时，我们发现这个上限是每层节点数的多项式，否则它是指数的。直观地说，一个复杂的分类问题——一个有许多“规则外的意外情况”的问题——需要一个复杂的决策边界来分离。

Tropical代数

Tropical Semiring $(R∪${$-∞$}$,⊕,⊙)$

Definition 2.2.1(Tropical加法，乘法，商)

加法：
$x ⊕ y := max(x, y)$
乘法：
$x ⊙ y := x + y$
商：
$x ⊘ y := x − y$
对于所有的$x∈ R$：
$−∞⊕x=x, −∞⊙x=−∞, 0⊙x=x.$
因此−∞是加法恒等元素，0是乘法恒等元素。
满足通用算数法则：
$x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z,$ $x ⊙ (y ⊙ z) = (x ⊙ y) ⊙ z.$ $x ⊕ y = y ⊕ x,$ $x ⊙ y = y ⊙ x.$ $x ⊙ (y ⊕ z) = (x ⊙ y) ⊕ (x ⊙ z).$
R∪{-∞}在运算符⊕和⊙下是半环，因为缺少加法逆元所以不是环，尽管如此，还是可以在Tropical半环中推广许多代数对象（矩阵、多项式、张量等）和概念（秩、行列式、次数等）。
Tropical 次幂：对于$a ∈ N,x ∈ R$
$x^{⊙a} :=\underbrace{x⊙···⊙x}_ {a\ times}=a·x(·表示普通乘法)$

注：本文之后的内容全部以$x^a$代替$x^{⊙a}$。

扩展到$R∪\{-∞\}$：

$−∞^{⊙a} := \lbrace_{0,if\ a\ =\ 0}^{−∞,if\ a\ >\ 0}$

Tropical乘法逆元：
$x^{⊙(-1)} := -x$
对于负数a ∈ Z：
$x^{⊙a} = (−x)^{⊙(−a)}$
另：−∞没有Tropical乘法逆元；当a < 0时，$−∞^{⊙a}$没有意义。
满足的规则：
1. For any x,y ∈ R and a ∈ N, $(x ⊕ y)^a = x^a ⊕ y^a.$
2. For any x,y ∈ R and a ∈ N, $(x ⊙ y)^a = x^a ⊙ y^a.$
3. For any x ∈ R, $x^0 = 0.$
4. For any x ∈ R and a,a′ ∈ N, $(x^a)^a′ = x^{a·a′}.$
5. For any x ∈ R and a,a′ ∈ Z, $x^a ⊙ x^a′ = x^{a+a′}.$
6. For any x ∈ R and a,a′ ∈ Z, $x^a⊕x^a′ = x^a⊙(x^{a−a′} ⊕ 0) = x^a ⊙ (0 ⊕ x^{a−a′}).$
Definition 2.2.2（Tropical monomial单项式）
$c⊙x_1^{a_1} ⊙ x_2^{a_2} ⊙···⊙ x_d^{a_d}$
where $c ∈ R ∪ {−∞}\ and\ a_1,…,a_d ∈ N$.

也可以方便地写成：
$cx^α$
where $α = (a_1,…,a_d) ∈ N^d\ and\ x = (x_1, . . . , x_d)$.

当然，对于Tropical乘法恒等元素0，有：
$x^α = 0 ⊙ x^α$
Definition 2.2.3（Tropical多项式）
$f(x)=c_1x^{α_1}⊕ . . .⊕ c_rx^{α_r}$
where $α_i = (a_{i1},…,a_{id}) ∈ N^d\ and\ c_i ∈ R ∪ {−∞}, i = 1,…,r$.
Definition 2.2.4（Tropical有理函数）
Tropical有理函数是两个Tropical多项式的差
$f(x) - g(x) = f(x) ⊘ g(x).$
Tropical多项式在⊕⊙运算下形成了一个半环，相似地，Tropical有理函数形成了一个半域。
Definition 2.2.5（Tropical多项式地图和Tropical有理地图）

Tropical hypersurface

Tropical多项式f的Tropical hypersurface是f在x上非线性的点x的集合。

Definition 2.3.1（Tropical hypersurface）

有一个Tropical多项式：

$$f(x)=c_1x^{α_1}⊕ . . .⊕ c_rx^{α_r}$$
Tropical hypersurface是集合：
$$T(f):=\ \{x∈R^d:c_ix^{α_i}=c_jx^{α_j} =f(x)\ for\ some\ α_i≠α_j\}.$$
换句话说，Tropical hypersurface包括了那些x,在x上的f的值由两个或两个以上单项式决定。
Tropical hypersurface把f分成线性的凸单元。